package com.LeetCode.String;

import org.junit.Test;

/**
 * 最长公共前缀
 */
public class LCP {

    private class TrieTree{

        private class TrieNode{
            int charCount;
            TrieNode[] children;
            public TrieNode(){
                charCount = 0;
                children = new TrieNode[26];
            }
        }

        private TrieNode root;

        public TrieTree(){
            root = new TrieNode();
        }

        public void insert(String word){
            TrieNode node = root;
            for(int i = 0; i<word.length(); i++){
                int index = word.charAt(i) - 'a';
                if(node.children[index] == null){
                    node.children[index] = new TrieNode();
                    node.charCount++;
                }
                node = node.children[index];
            }
            node.charCount++;
        }

        public boolean allStartWith(String prefix){
            TrieNode p = root;
            for(int i = 0; i<prefix.length(); i++){
                if(p.charCount > 1) return false;//尿分叉
                int index = prefix.charAt(i) - 'a';
                if(p.children[index] == null) return  false;//这个前缀不行
                p = p.children[index];
            }
            return true;
        }


    }

    public String longestCommonPrefix(String[] strs) {
        if(strs == null || strs.equals("")) return "";

        int len = strs[0].length();
        TrieTree tree = new TrieTree();
        for(String str : strs){
            tree.insert(str);
        }

        int l = 0, r = len;
        while(l<=r){
            int mid = (l+r)>>>1;
            if(tree.allStartWith(strs[0].substring(0,mid))){
                l = mid + 1;
            }else{
                r = mid - 1;
            }
        }
        return strs[0].substring(0,r);
    }

    @Test
    public void test(){
        String[] strs = {"flower","flow","flight"};
        System.out.println(longestCommonPrefix(strs));
    }
}
